package basis.netease.hard;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 7-3 拼接最大数
 * 给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。
 * 现在从这两个数组中选出 k (0 <=k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
 * 求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
 * 输入格式:
 * 输入三个行内容：
 * 第一行是数组nums1，元素内容用逗号分隔；数组最大长度为1000。
 * 第二行是数组nums2，元素内容用逗号分隔；数组最大长度为1000。
 * 第三行是长度k；
 * 输出格式:
 * 返回一个表示该最大数的长度为 k 的数组，数组元素用逗号隔开。
 * 输入样例:
 * 在这里给出一组输入。例如：
 * 3,4,6,5
 * 9,1,2,5,8,3
 * 5
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * 9,8,6,5,3
 * 提示：
 * 1 <= nums1.length, nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 9
 */
public class Main_3 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] nums1 = Arrays.stream(scanner.nextLine().split(",")).mapToInt(Integer::valueOf).toArray();
        int[] nums2 = Arrays.stream(scanner.nextLine().split(",")).mapToInt(Integer::valueOf).toArray();
        int k = scanner.nextInt();
        if (k == 0) {
            // 需要考虑这个边界值，不然一个用例过不了
            System.out.println("");
            return;
        }
        int[] result = maxNumber(nums1, nums2, k);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < result.length; i++) {
            sb.append(result[i] + ",");
        }
        System.out.println(sb.substring(0, sb.length() - 1));
    }

    public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] maxSubSeq = new int[k];
        for (int i = 0; i <= k && i <= nums1.length; i++) {
            if (k - i <= nums2.length) {
                int[] tmp = merge(maxSubSeq(nums1, i), maxSubSeq(nums2, k - i), k);
                if (compare(tmp, 0, maxSubSeq, 0)) {
                    maxSubSeq = tmp;
                }
            }
        }
        return maxSubSeq;
    }

    public static int[] maxSubSeq(int[] nums, int k) {
        int[] stack = new int[k];
        // 记录栈顶的索引位置
        int topIndex = -1;
        // 记录需要删除掉的个数
        int dropCount = nums.length - k;
        for (int i = 0; i < nums.length; i++) {
            // 如果需要删除的个数已经删除完毕，直接跳出循环
            int num = nums[i];
            while (topIndex >= 0 && stack[topIndex] < num && dropCount > 0) {
                topIndex--;
                dropCount--;
            }
            if (topIndex < k - 1) {
                stack[++topIndex] = num;
            } else {
                dropCount--;
            }
        }
        return stack;
    }

    public static int[] merge(int[] s1, int[] s2, int k) {
        if (s1.length == 0) {
            return s2;
        }
        if (s2.length == 0) {
            return s1;
        }
        int[] merged = new int[k];
        int index1 = 0, index2 = 0;
        for (int i = 0; i < k; i++) {
            if (compare(s1, index1, s2, index2)) {
                merged[i] = s1[index1++];
            } else {
                merged[i] = s2[index2++];
            }
        }
        return merged;
    }

    public static boolean compare(int[] s1, int index1, int[] s2, int index2) {
        if (index1 >= s1.length) {
            // s1的索引超出范围，则取s2
            return false;
        }
        if (index2 >= s2.length) {
            // s2的索引超出范围，则取s1
            return true;
        }
        if (s1[index1] > s2[index2]) {
            return true;
        }
        if (s1[index1] < s2[index2]) {
            return false;
        }
        // 值相等，就取下一个值比较
        return compare(s1, index1 + 1, s2, index2 + 1);
    }

}
